//
// Created by 高森森 on 2022/2/16.
//

#ifndef LEETCODE_SOLUTION51_H
#define LEETCODE_SOLUTION51_H
#include<iostream>
using namespace std;

#include <vector>
#include <queue>
class Solution51 {
public:
    double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
        vector<vector<int>>graph(n+1);
        for(auto &edge:edges){
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        vector<int>level(n+1);//记录层次
        vector<bool>isleaf(n+1,0);//记录是否是叶子节点,是为1，不是为0
        vector<bool>visited(n+1,0);//是否被访问过
        vector<double>prob(n+1);//每个点的概率
        queue<int>que;
        que.push(1);
        level[1]=0;
        visited[1]= true;
        while(!que.empty()){
            int node=que.front();
            que.pop();
            visited[node]= true;
            int len=graph[node].size();
            if(len==1)
            {
                isleaf[node]=1;
            }
            for(auto neigh:graph[node]){
                if(!visited[neigh]){
                    level[neigh]=level[node]+1;
                    que.push(neigh);
                    if(node==1){
                        prob[neigh]=1.0/(double)len;
                    }
                    else{
                        prob[neigh]=prob[node]*1.0/(double)(len-1);
                    }
                }
            }
        }
        if(level[target]>t){
            return 0;
        }
        else if(level[target]==t)
        {
            return prob[target];
        }
        else if(level[target]<t){
            if(isleaf[target])
                return prob[target];
            else
                return 0;
        }
        return 0;
    }
};


#endif //LEETCODE_SOLUTION51_H
